package lesson

// 二叉树排序算法，实现数组就地排序

type Node struct {
	value       int
	left, right *Node
}

func Sort(array []int) {
	var root *Node
	for _, value := range array {
		root = add(root, value)
	}
	appendValues(array[:0], root) // 使用 array[:0] 来清空数组并复用空间
}

// 追加数据
func add(n *Node, value int) *Node {
	if n == nil {
		return &Node{value: value}
	}
	if value > n.value {
		n.right = add(n.right, value)
	} else {
		n.left = add(n.left, value)
	}
	return n
}

func appendValues(array []int, root *Node) []int {
	if root != nil {
		array = appendValues(array, root.left)
		array = append(array, root.value)
		array = appendValues(array, root.right)
	}
	return array
}
